<!DOCTYPE html>
<html lang="en-us"><head>
    <meta charset='utf-8'>
    <meta name='viewport' content='width=device-width, initial-scale=1'><meta name='description' content='洛谷P2195 HXY造公园 因为洛谷上C语言题解比较少，所以我来一发题解(虽然这道题c语言和c&#43;&#43;都差不多&amp;hellip;)。
进入主题：
看题意题目会给出一个森林，我们首先需要处理出森林中每棵无向树的直径（直径：一棵树上两个节点距离的最大值），求解树的直径主要有两种方法：树状DP和跑两遍BFS，本文中用的是两遍bfs，对树状DP方法感兴趣的可以百度一下。
简单来说，第一遍bfs是找到距离根节点最远的节点，代码如下：
int dep[N];
dep[fa]=1;//fa是这棵树的根节点
int queue[N&amp;laquo;2],head=0,tail=1;
queue[0]=fa;
while(tail&amp;gt;head){
​ int u=queue[head&#43;&#43;];
for(int i=last[u];i;i=e[i].next){
​ int v=e[i].v;
​ root[v]=fa;//并查集，下面讲
​ if(!dep[v]){
​ dep[v]=dep[u]&#43;1;
​ queue[tail&#43;&#43;]=v;
​ }
}
}
s=queue[&amp;ndash;head];//s就是距离根节点最远的节点
找到s节点第一步就完成啦。
接下来第二步，从s节点出发，找出最大距离。。
int depp[N];
head=0;
tail=1;
depp[s]=1;
queue[0]=s;
while(tail&amp;gt;head){
​ int u=queue[head&#43;&#43;];
​ for(int i=last[u];i;i=e[i].next){
​ int v=e[i].v;
​ if(!depp[v]){
​ depp[v]=depp[u]&#43;1;
​ queue[tail&#43;&#43;]=v;
​ }
​ }
}
diameter[fa]=depp[queue[&amp;ndash;head]]-1;//di diameter[i]记录i节点所在的树的直径
那么怎么知道要以哪个点为顶点进行bfs，并且保证一棵树上的节点只bfs一次呢？
分离集(声明：分离集指的是并查集，下面就用分离集了)就派上用场了，在第一次bfs的时候我写了这样一条语句：root[v]=fa； 其中root[v]记录的是v点的祖先（不一保证是根节点），
比如在一棵树上，
D节点所在树的根节点为A，但是在某一时刻不保证root[D]存的是A而是B，但但是，只要root[B]存的是A，我们总有办法从D找到A，就算D节点的高度再大，有这样一条链在，我们都是能最终找到A的。回到第一次bfs，每一次有节点v进入队列queue，我们就将root[v]设置为fa，即这棵树上的根节点。进入bfs条件：'><title>括号匹配</title>
    
    <link rel='canonical' href='https://yanx57.gitee.io/solution/p/%E6%8B%AC%E5%8F%B7%E5%8C%B9%E9%85%8D/'>

<link rel="stylesheet" href="/solution/scss/style.min.css"><meta property='og:title' content='括号匹配'>
<meta property='og:description' content='洛谷P2195 HXY造公园 因为洛谷上C语言题解比较少，所以我来一发题解(虽然这道题c语言和c&#43;&#43;都差不多&amp;hellip;)。
进入主题：
看题意题目会给出一个森林，我们首先需要处理出森林中每棵无向树的直径（直径：一棵树上两个节点距离的最大值），求解树的直径主要有两种方法：树状DP和跑两遍BFS，本文中用的是两遍bfs，对树状DP方法感兴趣的可以百度一下。
简单来说，第一遍bfs是找到距离根节点最远的节点，代码如下：
int dep[N];
dep[fa]=1;//fa是这棵树的根节点
int queue[N&amp;laquo;2],head=0,tail=1;
queue[0]=fa;
while(tail&amp;gt;head){
​ int u=queue[head&#43;&#43;];
for(int i=last[u];i;i=e[i].next){
​ int v=e[i].v;
​ root[v]=fa;//并查集，下面讲
​ if(!dep[v]){
​ dep[v]=dep[u]&#43;1;
​ queue[tail&#43;&#43;]=v;
​ }
}
}
s=queue[&amp;ndash;head];//s就是距离根节点最远的节点
找到s节点第一步就完成啦。
接下来第二步，从s节点出发，找出最大距离。。
int depp[N];
head=0;
tail=1;
depp[s]=1;
queue[0]=s;
while(tail&amp;gt;head){
​ int u=queue[head&#43;&#43;];
​ for(int i=last[u];i;i=e[i].next){
​ int v=e[i].v;
​ if(!depp[v]){
​ depp[v]=depp[u]&#43;1;
​ queue[tail&#43;&#43;]=v;
​ }
​ }
}
diameter[fa]=depp[queue[&amp;ndash;head]]-1;//di diameter[i]记录i节点所在的树的直径
那么怎么知道要以哪个点为顶点进行bfs，并且保证一棵树上的节点只bfs一次呢？
分离集(声明：分离集指的是并查集，下面就用分离集了)就派上用场了，在第一次bfs的时候我写了这样一条语句：root[v]=fa； 其中root[v]记录的是v点的祖先（不一保证是根节点），
比如在一棵树上，
D节点所在树的根节点为A，但是在某一时刻不保证root[D]存的是A而是B，但但是，只要root[B]存的是A，我们总有办法从D找到A，就算D节点的高度再大，有这样一条链在，我们都是能最终找到A的。回到第一次bfs，每一次有节点v进入队列queue，我们就将root[v]设置为fa，即这棵树上的根节点。进入bfs条件：'>
<meta property='og:url' content='https://yanx57.gitee.io/solution/p/%E6%8B%AC%E5%8F%B7%E5%8C%B9%E9%85%8D/'>
<meta property='og:site_name' content='Yanxu'>
<meta property='og:type' content='article'><meta property='article:section' content='Post' /><meta property='article:published_time' content='2020-12-17T00:00:00&#43;00:00'/><meta property='article:modified_time' content='2020-12-17T00:00:00&#43;00:00'/><meta property='og:image' content='https://yanx57.gitee.io/solution/p/%E6%8B%AC%E5%8F%B7%E5%8C%B9%E9%85%8D/3.jpg' />
<meta name="twitter:title" content="括号匹配">
<meta name="twitter:description" content="洛谷P2195 HXY造公园 因为洛谷上C语言题解比较少，所以我来一发题解(虽然这道题c语言和c&#43;&#43;都差不多&amp;hellip;)。
进入主题：
看题意题目会给出一个森林，我们首先需要处理出森林中每棵无向树的直径（直径：一棵树上两个节点距离的最大值），求解树的直径主要有两种方法：树状DP和跑两遍BFS，本文中用的是两遍bfs，对树状DP方法感兴趣的可以百度一下。
简单来说，第一遍bfs是找到距离根节点最远的节点，代码如下：
int dep[N];
dep[fa]=1;//fa是这棵树的根节点
int queue[N&amp;laquo;2],head=0,tail=1;
queue[0]=fa;
while(tail&amp;gt;head){
​ int u=queue[head&#43;&#43;];
for(int i=last[u];i;i=e[i].next){
​ int v=e[i].v;
​ root[v]=fa;//并查集，下面讲
​ if(!dep[v]){
​ dep[v]=dep[u]&#43;1;
​ queue[tail&#43;&#43;]=v;
​ }
}
}
s=queue[&amp;ndash;head];//s就是距离根节点最远的节点
找到s节点第一步就完成啦。
接下来第二步，从s节点出发，找出最大距离。。
int depp[N];
head=0;
tail=1;
depp[s]=1;
queue[0]=s;
while(tail&amp;gt;head){
​ int u=queue[head&#43;&#43;];
​ for(int i=last[u];i;i=e[i].next){
​ int v=e[i].v;
​ if(!depp[v]){
​ depp[v]=depp[u]&#43;1;
​ queue[tail&#43;&#43;]=v;
​ }
​ }
}
diameter[fa]=depp[queue[&amp;ndash;head]]-1;//di diameter[i]记录i节点所在的树的直径
那么怎么知道要以哪个点为顶点进行bfs，并且保证一棵树上的节点只bfs一次呢？
分离集(声明：分离集指的是并查集，下面就用分离集了)就派上用场了，在第一次bfs的时候我写了这样一条语句：root[v]=fa； 其中root[v]记录的是v点的祖先（不一保证是根节点），
比如在一棵树上，
D节点所在树的根节点为A，但是在某一时刻不保证root[D]存的是A而是B，但但是，只要root[B]存的是A，我们总有办法从D找到A，就算D节点的高度再大，有这样一条链在，我们都是能最终找到A的。回到第一次bfs，每一次有节点v进入队列queue，我们就将root[v]设置为fa，即这棵树上的根节点。进入bfs条件："><meta name="twitter:card" content="summary_large_image">
	<meta name="twitter:image" content='https://yanx57.gitee.io/solution/p/%E6%8B%AC%E5%8F%B7%E5%8C%B9%E9%85%8D/3.jpg' /></head><body class="">
        <div class="container flex on-phone--column align-items--flex-start extended article-page with-toolbar">
            <aside class="sidebar left-sidebar sticky">
    <button class="hamburger hamburger--spin" type="button" id="toggle-menu" aria-label="">
        <span class="hamburger-box">
            <span class="hamburger-inner"></span>
        </span>
    </button>

    <header class="site-info">
        
            <figure class="site-avatar">
                

                
                    
                    <img src="/solution/img/1_hu24731bb07479c59d0174ed88b804ad56_582940_300x300_resize_box_2.png" width="300"
                        height="300" class="site-logo" loading="lazy" alt="Avatar">
                

                <span class="emoji">🐝</span>
            </figure>
        
        <h1 class="site-name"><a href="https://yanx57.gitee.io/solution">Yanxu</a></h1>
        <h2 class="site-description">铁砚磨穿</h2>
    </header>

    <ol class="menu" id="main-menu">
        
        
        

        <li >
            <a href='https://yanx57.gitee.io/solution/'>
                
                    <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-home" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <polyline points="5 12 3 12 12 3 21 12 19 12" />
  <path d="M5 12v7a2 2 0 0 0 2 2h10a2 2 0 0 0 2 -2v-7" />
  <path d="M9 21v-6a2 2 0 0 1 2 -2h2a2 2 0 0 1 2 2v6" />
</svg>



                
                <span>Home</span>
            </a>
        </li>
        
        

        <li >
            <a href='https://yanx57.gitee.io/solution/about'>
                
                    <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-user" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <circle cx="12" cy="7" r="4" />
  <path d="M6 21v-2a4 4 0 0 1 4 -4h4a4 4 0 0 1 4 4v2" />
</svg>



                
                <span>About me</span>
            </a>
        </li>
        
        

        <li >
            <a href='https://yanx57.gitee.io/solution/archives'>
                
                    <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-archive" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <rect x="3" y="4" width="18" height="4" rx="2" />
  <path d="M5 8v10a2 2 0 0 0 2 2h10a2 2 0 0 0 2 -2v-10" />
  <line x1="10" y1="12" x2="14" y2="12" />
</svg>



                
                <span>Archives</span>
            </a>
        </li>
        
    </ol>
</aside>
            <main class="main full-width">
    <div id="article-toolbar">
        <a href="https://yanx57.gitee.io/solution" class="back-home">
            <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-chevron-left" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <polyline points="15 6 9 12 15 18" />
</svg>



            <span>Back</span>
        </a>
    </div>

    <article class="has-image main-article">
    <header class="article-header">
        <div class="article-image">
            <img srcset="/solution/p/%E6%8B%AC%E5%8F%B7%E5%8C%B9%E9%85%8D/3_hud7e36f7e20e71be184458283bdae4646_55974_1024x0_resize_q75_box.jpg 1024w, /solution/p/%E6%8B%AC%E5%8F%B7%E5%8C%B9%E9%85%8D/3_hud7e36f7e20e71be184458283bdae4646_55974_2000x0_resize_q75_box.jpg 2000w"
                    src="/solution/p/%E6%8B%AC%E5%8F%B7%E5%8C%B9%E9%85%8D/3_hud7e36f7e20e71be184458283bdae4646_55974_2000x0_resize_q75_box.jpg" width="1000" height="667" loading="lazy"
                    alt="Featured image of post 括号匹配" />
            
        </div>
    

    <div class="article-details">
    
    <header class="article-category">
        
            <a href="https://yanx57.gitee.io/solution/categories/c/" 
                    class="color-tag"
                    data-image="/solution/p/%E6%8B%AC%E5%8F%B7%E5%8C%B9%E9%85%8D/3_hud7e36f7e20e71be184458283bdae4646_55974_20x20_fill_q75_box_smart1.jpg" 
                    data-key="" 
                    data-hash="md5-xRTZFpFxc6SKQuARS0aZYQ==">
                    C
                </a>
            
        
            <a href="https://yanx57.gitee.io/solution/categories/bfs/" 
                    class="color-tag"
                    data-image="/solution/p/%E6%8B%AC%E5%8F%B7%E5%8C%B9%E9%85%8D/3_hud7e36f7e20e71be184458283bdae4646_55974_20x20_fill_q75_box_smart1.jpg" 
                    data-key="" 
                    data-hash="md5-xRTZFpFxc6SKQuARS0aZYQ==">
                    bfs
                </a>
            
        
            <a href="https://yanx57.gitee.io/solution/categories/%E5%B9%B6%E6%9F%A5%E9%9B%86/" 
                    class="color-tag"
                    data-image="/solution/p/%E6%8B%AC%E5%8F%B7%E5%8C%B9%E9%85%8D/3_hud7e36f7e20e71be184458283bdae4646_55974_20x20_fill_q75_box_smart1.jpg" 
                    data-key="" 
                    data-hash="md5-xRTZFpFxc6SKQuARS0aZYQ==">
                    并查集
                </a>
            
        
            <a href="https://yanx57.gitee.io/solution/categories/%E6%A0%91%E7%9A%84%E7%9B%B4%E5%BE%84/" 
                    class="color-tag"
                    data-image="/solution/p/%E6%8B%AC%E5%8F%B7%E5%8C%B9%E9%85%8D/3_hud7e36f7e20e71be184458283bdae4646_55974_20x20_fill_q75_box_smart1.jpg" 
                    data-key="" 
                    data-hash="md5-xRTZFpFxc6SKQuARS0aZYQ==">
                    树的直径
                </a>
            
        
    </header>
    

    <h2 class="article-title">
        <a href="https://yanx57.gitee.io/solution/p/%E6%8B%AC%E5%8F%B7%E5%8C%B9%E9%85%8D/">括号匹配</a>
    </h2>

    <footer class="article-time">
        <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-clock" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <circle cx="12" cy="12" r="9" />
  <polyline points="12 7 12 12 15 15" />
</svg>



        <time class="article-time--published">2020 Dec 17</time>
    </footer></div>
</header>

    <section class="article-content">
    <h2 id="洛谷p2195-hxy造公园">洛谷P2195 HXY造公园</h2>
<p>因为洛谷上C语言题解比较少，所以我来一发题解(虽然这道题c语言和c++都差不多&hellip;)。</p>
<p>进入主题：</p>
<p>看题意题目会给出一个森林，我们首先需要处理出森林中每棵无向树的直径（直径：一棵树上两个节点距离的最大值），求解树的直径主要有两种方法：树状DP和跑两遍BFS，本文中用的是两遍bfs，对树状DP方法感兴趣的可以百度一下。</p>
<p>简单来说，第一遍bfs是找到距离根节点最远的节点，代码如下：</p>
<p><strong>int</strong> dep[N];</p>
<p>dep[fa]=1;//fa是这棵树的根节点</p>
<p><strong>int</strong> queue[N&laquo;2],head=0,tail=1;</p>
<p>queue[0]=fa;</p>
<p><strong>while</strong>(tail&gt;head){</p>
<p>​    <strong>int</strong> u=queue[head++];</p>
<p><strong>for</strong>(<strong>int</strong> i=last[u];i;i=e[i].next){</p>
<p>​    <strong>int</strong> v=e[i].v;</p>
<p>​    root[v]=fa;//并查集，下面讲</p>
<p>​    <strong>if</strong>(!dep[v]){</p>
<p>​      dep[v]=dep[u]+1;</p>
<p>​      queue[tail++]=v;</p>
<p>​    }</p>
<p>}</p>
<p>}</p>
<p>s=queue[&ndash;head];//s就是距离根节点最远的节点</p>
<p>找到s节点第一步就完成啦。</p>
<p>接下来第二步，从s节点出发，找出最大距离。。</p>
<p><strong>int</strong> depp[N];</p>
<p>head=0;</p>
<p>tail=1;</p>
<p>depp[s]=1;</p>
<p>queue[0]=s;</p>
<p><strong>while</strong>(tail&gt;head){</p>
<p>​    <strong>int</strong> u=queue[head++];</p>
<p>​    <strong>for</strong>(<strong>int</strong> i=last[u];i;i=e[i].next){</p>
<p>​      <strong>int</strong> v=e[i].v;</p>
<p>​      <strong>if</strong>(!depp[v]){</p>
<p>​        depp[v]=depp[u]+1;</p>
<p>​        queue[tail++]=v;</p>
<p>​      }</p>
<p>​    }</p>
<p>}</p>
<p>diameter[fa]=depp[queue[&ndash;head]]-1;//di diameter[i]记录i节点所在的树的直径</p>
<p>那么怎么知道要以哪个点为顶点进行bfs，并且保证一棵树上的节点只bfs一次呢？</p>
<p>分离集(声明：分离集指的是并查集，下面就用分离集了)就派上用场了，在第一次bfs的时候我写了这样一条语句：root[v]=fa； 其中root[v]记录的是v点的祖先（不一保证是根节点），</p>
<p>比如在一棵树上，</p>
<p><img src="https://yanx57.gitee.io/photo/tree.jpg" alt="1"  /></p>
<p>D节点所在树的根节点为A，但是在某一时刻不保证root[D]存的是A而是B，但但是，只要root[B]存的是A，我们总有办法从D找到A，就算D节点的高度再大，有这样一条链在，我们都是能最终找到A的。回到第一次bfs，每一次有节点v进入队列queue，我们就将root[v]设置为fa，即这棵树上的根节点。进入bfs条件：</p>
<p><strong>for</strong>(<strong>int</strong> i=1;i&lt;=n;i++){</p>
<p>​    <strong>if</strong>(root[i]==i&amp;&amp;alone[i]){//alone[i]为0表示i是一个孤立点，孤立点就没必要bfs了</p>
<p>​      bfs1(i);</p>
<p>​    }</p>
<p>}</p>
<p>接下来，查询操作，直接输出数组diameter对应的记录就好。</p>
<p>合并操作，可以推出：对于两个点u,v,它们的根节点分别是rootu，rootv，将rootv为根的树合并到rootu为根的树中，显然，在rootv为根的树中的最长路径的中点，向rootu为根的树中的最长路径的中点建边，得到的树的直径会最小，可以证明：</p>
<p>设rootu为根的树直径为l1,rootv为根的树直径为l2,将l1和l2都分为两部分：</p>
<p>x1,x2,x3,x4,则x1+x2=l1,x3+x4=l2,假设x1&gt;=x2,x3&gt;=x4,则x1+x3&gt;=1/2✖️l1的上取整+1/2✖️l2的上取整，c语言可以写成为1/2(l1+1)+1/2(l2+1),再与原来合并前的两个树的直径取最大值即可。</p>
<p>完整代码：</p>
<p>#include&lt;stdio.h&gt;</p>
<p>#include&lt;string.h&gt;</p>
<p>#include&lt;stdlib.h&gt;</p>
<p>#include&lt;limits.h&gt;</p>
<p>#include&lt;stdbool.h&gt;</p>
<p>#define N 300050</p>
<p>#define M 300050</p>
<p><strong>int</strong> n,m,q;</p>
<p><strong>int</strong> root[N],diameter[N],alone[N];</p>
<p><strong>struct</strong> edge{</p>
<p><strong>int</strong> u,v;</p>
<p><strong>int</strong> next;</p>
<p>}e[M&laquo;2];</p>
<p><strong>int</strong> last[N],tot=0;</p>
<p><strong>void</strong> addEdge(<strong>int</strong> u,<strong>int</strong> v){</p>
<p>e[++tot].u=u;e[tot].v=v;</p>
<p>e[tot].next=last[u];last[u]=tot;</p>
<p>}</p>
<p><strong>int</strong> find(<strong>int</strong> x){</p>
<p><strong>if</strong>(root[x]==x) <strong>return</strong> x;</p>
<p>root[x]=find(root[x]);</p>
<p><strong>return</strong> root[x];</p>
<p>}</p>
<p><strong>int</strong> max(<strong>int</strong> x,<strong>int</strong> y){</p>
<p><strong>return</strong> x&gt;y?x:y;</p>
<p>}</p>
<p><strong>int</strong> min(<strong>int</strong> x,<strong>int</strong> y){</p>
<p><strong>return</strong> x&lt;y?x:y;</p>
<p>}</p>
<p><strong>int</strong> s;</p>
<p><strong>void</strong> bfs1(<strong>int</strong> fa){</p>
<p><strong>int</strong> dep[N];</p>
<p>dep[fa]=1;</p>
<p><strong>int</strong> queue[N&laquo;2],head=0,tail=1;</p>
<p>queue[0]=fa;</p>
<p><strong>while</strong>(tail&gt;head){</p>
<p>​    <strong>int</strong> u=queue[head++];</p>
<p><strong>for</strong>(<strong>int</strong> i=last[u];i;i=e[i].next){</p>
<p>​    <strong>int</strong> v=e[i].v;</p>
<p>​    root[v]=fa;</p>
<p>​    <strong>if</strong>(!dep[v]){</p>
<p>​      dep[v]=dep[u]+1;</p>
<p>​      queue[tail++]=v;</p>
<p>​    }</p>
<p>}</p>
<p>}</p>
<p>s=queue[&ndash;head];</p>
<p><strong>int</strong> depp[N];</p>
<p>head=0;</p>
<p>tail=1;</p>
<p>depp[s]=1;</p>
<p>queue[0]=s;</p>
<p><strong>while</strong>(tail&gt;head){</p>
<p>​    <strong>int</strong> u=queue[head++];</p>
<p>​    <strong>for</strong>(<strong>int</strong> i=last[u];i;i=e[i].next){</p>
<p>​      <strong>int</strong> v=e[i].v;</p>
<p>​      <strong>if</strong>(!depp[v]){</p>
<p>​        depp[v]=depp[u]+1;</p>
<p>​        queue[tail++]=v;</p>
<p>​      }</p>
<p>​    }</p>
<p>}</p>
<p>diameter[fa]=depp[queue[&ndash;head]]-1;</p>
<p>}</p>
<p><strong>int</strong> quickRead(){</p>
<p><strong>int</strong> a=0,b=1;</p>
<p><strong>char</strong> ch=getchar();</p>
<p><strong>while</strong>((ch&gt;&lsquo;9&rsquo;||ch&lt;&lsquo;0&rsquo;)&amp;&amp;ch!='-') ch=getchar();</p>
<p><strong>if</strong>(ch=='-') {b=-1;ch=getchar();}</p>
<p><strong>while</strong>(ch&gt;=&lsquo;0&rsquo;&amp;&amp;ch&lt;=&lsquo;9&rsquo;) {a=a*10+ch-&lsquo;0&rsquo;;ch=getchar();}</p>
<p><strong>return</strong> a*b;</p>
<p>}</p>
<p><strong>int</strong> main(){</p>
<p>n=quickRead();m=quickRead();q=quickRead();</p>
<p><strong>int</strong> p,u,v;</p>
<p><strong>for</strong>(<strong>int</strong> i=1;i&lt;=n;i++) root[i]=i;</p>
<p><strong>for</strong>(<strong>int</strong> i=1;i&lt;=m;i++){</p>
<p>​    u=quickRead();v=quickRead();</p>
<p>​    alone[u]=1;</p>
<p>​    alone[v]=1;</p>
<p>​    addEdge(u, v);</p>
<p>​    addEdge(v, u);</p>
<p>}</p>
<p><strong>for</strong>(<strong>int</strong> i=1;i&lt;=n;i++){</p>
<p>​    <strong>if</strong>(root[i]==i&amp;&amp;alone[i]){</p>
<p>​      bfs1(i);</p>
<p>​    }</p>
<p>}</p>
<p><strong>for</strong>(<strong>int</strong> i=1;i&lt;=q;i++){</p>
<p>​    p=quickRead();</p>
<p>​    <strong>if</strong>(p==1){</p>
<p>​      u=quickRead();</p>
<p>​      printf(&quot;%d\n&quot;,diameter[find(root[u])]);</p>
<p>​    }<strong>else</strong>{</p>
<p>​      u=quickRead();v=quickRead();</p>
<p>​      <strong>int</strong> rootu=find(u);</p>
<p>​      <strong>int</strong> rootv=find(v);</p>
<p>​      <strong>if</strong>(rootu!=rootv){</p>
<p>​        <strong>int</strong> l1=diameter[rootu],l2=diameter[rootv];</p>
<p>​        diameter[rootu]=max(((l1+1)&raquo;1)+((l2+1)&raquo;1)+1,max(l1,l2));</p>
<p>​        root[rootv]=rootu;</p>
<p>​      }</p>
<p>​    }</p>
<p>}</p>
<p><strong>return</strong> 0;</p>
<p>}</p>

</section>


    <footer class="article-footer">
    

    </footer>

    
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/katex.min.css"
    integrity="sha384-AfEj0r4/OFrOo5t7NnNe46zW/tFgW6x/bCJG8FqQCEo3+Aro6EYUG4+cU+KJWu/X" crossorigin="anonymous">
<script defer src="https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/katex.min.js"
    integrity="sha384-g7c+Jr9ZivxKLnZTDUhnkOnsh30B4H0rpLUpJ4jAIKs4fnJI+sEnkvrMWph2EDg4"
    crossorigin="anonymous"></script>
<script defer src="https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/contrib/auto-render.min.js"
    integrity="sha384-mll67QQFJfxn0IYznZYonOWZ644AWYC+Pt2cHqMaRhXVrursRwvLnLaebdGIlYNa" crossorigin="anonymous"
    onload="renderMathInElement(document.querySelector(`.article-content`));"></script>
    
</article>

    <aside class="related-contents--wrapper">
    
    
</aside>

    
        
    

    <footer class="site-footer">
    <section class="copyright">&copy; 2020 Yanxu</section>
    <section class="powerby">
        Built with <a href="https://gohugo.io/" target="_blank" rel="noopener">Hugo</a> <br />
        Theme <b><a href="https://github.com/CaiJimmy/hugo-theme-stack" target="_blank" rel="noopener" data-version="1.0.5">Stack</a></b> designed by
        <a href="https://jimmycai.com" target="_blank" rel="noopener">Jimmy</a>
    </section>
</footer>
<div class="pswp" tabindex="-1" role="dialog" aria-hidden="true" style="display:none">

    
    <div class="pswp__bg"></div>

    
    <div class="pswp__scroll-wrap">

        
        <div class="pswp__container">
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
        </div>

        
        <div class="pswp__ui pswp__ui--hidden">

            <div class="pswp__top-bar">

                

                <div class="pswp__counter"></div>

                <button class="pswp__button pswp__button--close" title="Close (Esc)"></button>

                <button class="pswp__button pswp__button--share" title="Share"></button>

                <button class="pswp__button pswp__button--fs" title="Toggle fullscreen"></button>

                <button class="pswp__button pswp__button--zoom" title="Zoom in/out"></button>

                
                
                <div class="pswp__preloader">
                    <div class="pswp__preloader__icn">
                        <div class="pswp__preloader__cut">
                            <div class="pswp__preloader__donut"></div>
                        </div>
                    </div>
                </div>
            </div>

            <div class="pswp__share-modal pswp__share-modal--hidden pswp__single-tap">
                <div class="pswp__share-tooltip"></div>
            </div>

            <button class="pswp__button pswp__button--arrow--left" title="Previous (arrow left)">
            </button>

            <button class="pswp__button pswp__button--arrow--right" title="Next (arrow right)">
            </button>

            <div class="pswp__caption">
                <div class="pswp__caption__center"></div>
            </div>

        </div>

    </div>

</div>
            </main>
        </div>
        <script src="https://cdn.jsdelivr.net/npm/node-vibrant@3.1.5/dist/vibrant.min.js"
    integrity="sha256-5NovOZc4iwiAWTYIFiIM7DxKUXKWvpVEuMEPLzcm5/g=" crossorigin="anonymous"></script><script type="text/javascript" src="/solution/ts/main.js" defer></script>
<script>
    (function () {
        const customFont = document.createElement('link');
        customFont.href = "https://fonts.googleapis.com/css2?family=Lato:wght@300;400;700&display=swap";

        customFont.type = "text/css";
        customFont.rel = "stylesheet";

        document.head.appendChild(customFont);
    }());
</script>
<link rel="stylesheet" href="/solution/css/highlight/light.min.css" media="(prefers-color-scheme: light)">
<link rel="stylesheet" href="/solution/css/highlight/dark.min.css" media="(prefers-color-scheme: dark)">

    </body>
</html>
